import java.util.Arrays;
import java.util.Objects;


// 使用泛型实现一个自定义的模拟hashMap，注意需要重写equals和hashCode
class MyHashMap2<K,V>{
    static class Node<K,V> {
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node<K,V>[] array = (Node<K, V>[]) new Node[8];
    public int usedSize = 0;


    // 计算并返回负载因子
    private float loadFactor(){
        return usedSize*1.0f/array.length;
    }
    // 负载因子>=0.75时，扩容数组长度，并将链表中的节点重新哈希
    private void resize() {
        Node<K,V>[] newArray = (Node<K, V>[]) new Node[2*array.length];
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null){
                Node<K,V> curNext = cur.next;
                int indexResize = cur.key.hashCode() % newArray.length;

                cur.next = newArray[indexResize];
                newArray[indexResize] = cur;
                cur = curNext;
            }
        }
        array = newArray;
    }

    // 新增元素
    public void put(K k, V v){
        // 1.通过key和hash函数计算新增节点在数组上的下标下的链表，查找是否有相同的key，有则替换
        int indexAdd = k.hashCode() % array.length; // 注意1：要保证同一个key的hashCode相同，那就得重写hashCode。
        Node<K,V> cur = array[indexAdd];
        while(cur != null){
            if(cur.key.equals(k)){       // 注意2：要重写equals方法，确定以key的什么属性作为比较
                cur.val = v;
                return;
            }
            cur = cur.next;
        }
        // 2.没有相同的key，则使用头插法插入新节点,然后usedSize++
        Node<K,V> newNode = new Node<>(k,v);
        newNode.next = array[indexAdd];
        array[indexAdd] = newNode;
        ++usedSize;
        // 3.如果负载因子大于等于0.75，每个结点重新哈希。
        if(loadFactor() >= 0.75){
            resize();
        }
    }
    public V get(K k){
        int indexGet = k.hashCode() % array.length;
        Node<K,V> cur = array[indexGet];
        while (cur != null){
            if(cur.key.equals(k)){
                return cur.val;
            }
            cur = cur.next;
        }

        return null;
    }

}

public class Main {
    public static void main(String[] args) {
        MyHashMap2<Student,Integer> map = new MyHashMap2<>();
        map.put(new Student("2","er"),1);
        map.put(new Student("8","ba"),1);
        map.put(new Student("3","san"),1);
        map.put(new Student("10","shi"),1);
        map.put(new Student("4","si"),1);
        map.put(new Student("18","shiba"),1);
        map.put(new Student("13","shisan"),1);

        System.out.println(map.get(new Student("2","er")));
    }
}
